package frist50;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class T0017 {
    public List<String> letterCombinations(String digits) {
        String[] strs={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        LinkedList<String> deque=new LinkedList<>();
        deque.add("");
        for (int i = 0; i <digits.length() ; i++) {
            char c=digits.charAt(i);
            int n=Integer.parseInt(String.valueOf(c))-2;
            int size=deque.size();
            for (int j = 0; j <size ; j++) {
                String str=deque.poll();
                for (int k = 0; k <strs[n].length() ; k++) {
                    deque.add(str+strs[n].charAt(k));
                }
            }
        }
        if(deque.peek()=="")return new LinkedList<>();
        int size=deque.size();
        List<String> re=deque;
        for (int i = 0; i <size ; i++) {
            re.add(deque.poll());
        }
        return re;
    }
}
